<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  
  <title>数据结构快速盘点 | lucifer的网络博客</title>
  
  <meta name="keywords" content="前端 leetocde 数据结构 算法 lucifer 大前端 性能优化 前端架构 前端工程化">
  
  
  <meta name="description" content="lucifer的个人博客，用来记录LeeCode刷题过程和心得，以及构建大前端知识体系">
  

  
  <link rel="alternate" href="/blog/atom.xml" title="lucifer的网络博客">
  

  <meta name="HandheldFriendly" content="True">
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <!-- meta -->
  

  <!-- link -->
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.10.1/css/all.min.css">
  

  
  <link rel="shortcut icon" type="image/x-icon" href="https://avatars0.githubusercontent.com/u/12479470?s=400&u=442571e44cbd0b67e3503e9551d4445c78f593f8&v=4">
  

  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.9.9/css/style.css">
  

  <script>
    function setLoadingBarProgress(num) {
      document.getElementById('loading-bar').style.width=num+"%";
    }
  </script>

  
    <!-- Global site tag (gtag.js) - Google Analytics -->
    <script async src="https://www.googletagmanager.com/gtag/js?id=G-FVTTYT432Q"></script>
    <script>
      window.dataLayer = window.dataLayer || [];
      function gtag(){dataLayer.push(arguments);}
      gtag('js', new Date());
      gtag('config', 'G-FVTTYT432Q');
    </script>
  
  
    <!-- ba -->
    <script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?576ec211e11a69128667eb8c11a6cffe";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
    </script>
  
</head>

<body>
  
  
  <div class="cover-wrapper">
    <cover class='cover post half'>
      
        
  <h1 class='title'>lucifer</h1>


  <div class="m_search">
    <form name="searchform" class="form u-search-form">
      <input type="text" class="input u-search-input" placeholder="" />
      <i class="icon fas fa-search fa-fw"></i>
    </form>
  </div>

<div class='menu navgation'>
  <ul class='h-list'>
    
      
        <li>
          <a class="nav home" href="/blog/"
            
            
            id="blog">
            <i class='fas fa-home fa-fw'></i>&nbsp;主页
          </a>
        </li>
      
        <li>
          <a class="nav home" href="http://leetcode-solution.cn/"
            
            
            id="http:leetcode-solution.cn">
            <i class='fas fa-laptop-code fa-fw'></i>&nbsp;官网
          </a>
        </li>
      
        <li>
          <a class="nav home" href="/blog/friends/"
            
            
            id="blogfriends">
            <i class='fas fa-link fa-fw'></i>&nbsp;友链
          </a>
        </li>
      
        <li>
          <a class="nav home" href="/blog/about/"
            
            
            id="blogabout">
            <i class='fas fa-id-card-alt fa-fw'></i>&nbsp;联系我
          </a>
        </li>
      
    
  </ul>
</div>

      
    </cover>
    <header class="l_header pure">
  <div id="loading-bar-wrapper">
    <div id="loading-bar" class="pure"></div>
  </div>

	<div class='wrapper'>
		<div class="nav-main container container--flex">
      <a class="logo flat-box" href='/blog/' >
        
          lucifer的网络博客
        
      </a>
			<div class='menu navgation'>
				<ul class='h-list'>
          
  					
  						<li>
								<a class="nav flat-box" href="/blog/"
                  
                  
                  id="blog">
									<i class='fas fa-grin fa-fw'></i>&nbsp;回到主页
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/blog/categories/"
                  
                  
                  id="blogcategories">
									<i class='fas fa-folder-open fa-fw'></i>&nbsp;分类
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/blog/tags/"
                  
                  
                  id="blogtags">
									<i class='fas fa-hashtag fa-fw'></i>&nbsp;标签
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/blog/archives/"
                  
                  
                  id="blogarchives">
									<i class='fas fa-archive fa-fw'></i>&nbsp;归档
								</a>
							</li>
      			
      		
				</ul>
			</div>

			
				<div class="m_search">
					<form name="searchform" class="form u-search-form">
						<input type="text" class="input u-search-input" placeholder="搜索" />
						<i class="icon fas fa-search fa-fw"></i>
					</form>
				</div>
			
			<ul class='switcher h-list'>
				
					<li class='s-search'><a class="fas fa-search fa-fw" href='javascript:void(0)'></a></li>
				
				<li class='s-menu'><a class="fas fa-bars fa-fw" href='javascript:void(0)'></a></li>
			</ul>
		</div>

		<div class='nav-sub container container--flex'>
			<a class="logo flat-box"></a>
			<ul class='switcher h-list'>
				<li class='s-comment'><a class="flat-btn fas fa-comments fa-fw" href='javascript:void(0)'></a></li>
        
          <li class='s-toc'><a class="flat-btn fas fa-list fa-fw" href='javascript:void(0)'></a></li>
        
			</ul>
		</div>
	</div>
</header>
	<aside class="menu-phone">
    <header>
		<nav class="menu navgation">
      <ul>
        
          
            <li>
							<a class="nav flat-box" href="/blog/"
                
                
                id="blog">
								<i class='fas fa-clock fa-fw'></i>&nbsp;近期文章
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/archives/"
                
                
                id="blogarchives">
								<i class='fas fa-archive fa-fw'></i>&nbsp;文章归档
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/about/"
                
                
                id="blogabout">
								<i class='fas fa-info-circle fa-fw'></i>&nbsp;关于小站
							</a>
            </li>
          
       
      </ul>
		</nav>
    </header>
	</aside>
<script>setLoadingBarProgress(40);</script>

  </div>


  <div id="container" class="l_body">
    <div class='body-wrapper'>
      <div class='l_main'>
  

  <article id="post" class="post white-box article-type-post" itemscope itemprop="blogPost">
    


  <section class='meta'>
    
    
    <div class="meta" id="header-meta">
      
        
  
    <h1 class="title">
      <a href="/blog/2020/01/03/basic-data-structure/">
        数据结构快速盘点
      </a>
    </h1>
  


      
      <div class='new-meta-box'>
        
          
        
          
            
  <div class='new-meta-item author'>
    
      <a href="https://lucifer.ren/blog" rel="nofollow">
        
          <img src="https://avatars0.githubusercontent.com/u/12479470?s=400&u=442571e44cbd0b67e3503e9551d4445c78f593f8&v=4">
        
        <p>lucifer</p>
      </a>
    
  </div>


          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt" aria-hidden="true"></i>
    <p>2020-01-03</p>
  </a>
</div>

          
        
          
            
  
  <div class='new-meta-item category'>
    <a href='/blog/categories/数据结构/' rel="nofollow">
      <i class="fas fa-folder-open" aria-hidden="true"></i>
      <p>数据结构</p>
    </a>
  </div>


          
        
          
            
  
    <div class="new-meta-item browse busuanzi">
      <a class='notlink'>
        <i class="fas fa-eye" aria-hidden="true"></i>
        <p>
          <span id="busuanzi_value_page_pv">
            <i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i>
          </span>
        </p>
      </a>
    </div>
  


          
        
          
            

          
        
          
            
  
    <div style="margin-right: 10px;">
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-keyboard"></i>
          <span class="post-meta-item-text">  字数统计: </span>
          <span class="post-count">6k字</span>
        </span>
      </span>
      &nbsp; | &nbsp;
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-hourglass-half"></i>
          <span class="post-meta-item-text">  阅读时长≈</span>
          <span class="post-count">21分</span>
        </span>
      </span>
    </div>
  

          
        
      </div>
      
        <hr>
      
    </div>
  </section>


    <section class="article typo">
      <div class="article-entry" itemprop="articleBody">
        <p>这篇文章不是讲解数据结构的文章，而是结合现实的场景帮助大家<code>理解和复习</code>数据结构与算法，<br>如果你的数据结构基础很差，建议先去看一些基础教程，再转过来看。</p>
<p>本篇文章的定位是侧重于前端的，通过学习前端中实际场景的数据结构，从而加深大家对数据结构的理解和认识。</p>
<a id="more"></a>

<h2 id="线性结构"><a href="#线性结构" class="headerlink" title="线性结构"></a>线性结构</h2><p>数据结构我们可以从逻辑上分为线性结构和非线性结构。线性结构有<br>数组，栈，链表等， 非线性结构有树，图等。</p>
<blockquote>
<p>其实我们可以称树为一种半线性结构。</p>
</blockquote>
<p>需要注意的是，线性和非线性不代表存储结构是线性的还是非线性的，这两者没有任何关系，它只是一种逻辑上的划分。<br>比如我们可以用数组去存储二叉树。</p>
<p>一般而言，有前驱和后继的就是线性数据结构。比如数组和链表。其实一叉树就是链表。</p>
<h3 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h3><p>数组是最简单的数据结构了，很多地方都用到它。 比如有一个数据列表等，用它是再合适不过了。<br>其实后面的数据结构很多都有数组的影子。</p>
<p>我们之后要讲的栈和队列其实都可以看成是一种<code>受限</code>的数组, 怎么个受限法呢？我们后面讨论。</p>
<p>我们来讲几个有趣的例子来加深大家对数组这种数据结构的理解。</p>
<h4 id="React-Hooks"><a href="#React-Hooks" class="headerlink" title="React Hooks"></a>React Hooks</h4><p>Hooks 的本质就是一个数组， 伪代码：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji13k55rj30m80bsq3j.jpg" alt></p>
<p>那么为什么 hooks 要用数组？ 我们可以换个角度来解释，如果不用数组会怎么样？</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Form</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="comment">// 1. Use the name state variable</span></span><br><span class="line">  <span class="keyword">const</span> [name, setName] = useState(<span class="string">"Mary"</span>);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 2. Use an effect for persisting the form</span></span><br><span class="line">  useEffect(<span class="function"><span class="keyword">function</span> <span class="title">persistForm</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">    localStorage.setItem(<span class="string">"formData"</span>, name);</span><br><span class="line">  &#125;);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 3. Use the surname state variable</span></span><br><span class="line">  <span class="keyword">const</span> [surname, setSurname] = useState(<span class="string">"Poppins"</span>);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 4. Use an effect for updating the title</span></span><br><span class="line">  useEffect(<span class="function"><span class="keyword">function</span> <span class="title">updateTitle</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">    <span class="built_in">document</span>.title = name + <span class="string">" "</span> + surname;</span><br><span class="line">  &#125;);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// ...</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>基于数组的方式，Form 的 hooks 就是 [hook1, hook2, hook3, hook4],<br>我们可以得出这样的关系， hook1 就是[name, setName] 这一对，<br>hook2 就是 persistForm 这个。</p>
<p>如果不用数组实现，比如对象，Form 的 hooks 就是</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">&#123;</span><br><span class="line">  <span class="string">'key1'</span>: hook1,</span><br><span class="line">  <span class="string">'key2'</span>: hook2,</span><br><span class="line">  <span class="string">'key3'</span>: hook3,</span><br><span class="line">  <span class="string">'key4'</span>: hook4,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>那么问题是 key1，key2，key3，key4 怎么取呢？</p>
<p>关于 React hooks 的本质研究，更多请查看<a href="https://medium.com/@ryardley/react-hooks-not-magic-just-arrays-cd4f1857236e" target="_blank" rel="noopener">React hooks: not magic, just arrays</a></p>
<p>React 将<code>如何确保组件内部hooks保存的状态之间的对应关系</code>这个工作交给了<br>开发人员去保证，即你必须保证 HOOKS 的顺序严格一致，具体可以看 React 官网关于 Hooks Rule 部分。</p>
<h3 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h3><p>队列是一种受限的序列，它只能够操作队尾和队首，并且只能只能在队尾添加元素，在队首删除元素。</p>
<p>队列作为一种最常见的数据结构同样有着非常广泛的应用， 比如消息队列</p>
<blockquote>
<p>“队列”这个名称,可类比为现实生活中排队（不插队的那种）</p>
</blockquote>
<p>在计算机科学中, 一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。</p>
<p>队列基本操作有两种:</p>
<ul>
<li>向队列的后端位置添加实体，称为入队</li>
<li>从队列的前端位置移除实体，称为出队。</li>
</ul>
<p>队列中元素先进先出 FIFO (first in, first out)的示意：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji2c8g4uj30b107lmxa.jpg" alt></p>
<p>(图片来自 <a href="https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/queue/README.zh-CN.md" target="_blank" rel="noopener">https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/queue/README.zh-CN.md</a>)</p>
<p>我们前端在做性能优化的时候，很多时候会提到的一点就是“HTTP 1.1 的队头阻塞问题”，具体来说<br>就是 HTTP2 解决了 HTTP1.1 中的队头阻塞问题，但是为什么 HTTP1.1 有队头阻塞问题，HTTP2 究竟怎么解决的很多人都不清楚。</p>
<p>其实“队头阻塞”是一个专有名词，不仅仅这里有，交换器等其他都有这个问题，引起这个问题的根本原因是使用了<code>队列</code>这种数据结构。</p>
<p>对于同一个 tcp 连接，所有的 http1.0 请求放入队列中，只有前一个<code>请求的响应</code>收到了，然后才能发送下一个请求，这个阻塞主要发生在客户端。</p>
<p>这就好像我们在等红绿灯，即使旁边绿灯亮了，你的这个车道是红灯，你还是不能走，还是要等着。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji2whipnj30gf0e2dgm.jpg" alt></p>
<p><code>HTTP/1.0</code> 和 <code>HTTP/1.1</code>:<br>在<code>HTTP/1.0</code> 中每一次请求都需要建立一个 TCP 连接，请求结束后立即断开连接。<br>在<code>HTTP/1.1</code> 中，每一个连接都默认是长连接(persistent connection)。对于同一个 tcp 连接，允许一次发送多个 http1.1 请求，也就是说，不必等前一个响应收到，就可以发送下一个请求。这样就解决了 http1.0 的客户端的队头阻塞，而这也就是<code>HTTP/1.1</code>中<code>管道(Pipeline)</code>的概念了。<br>但是，<code>http1.1规定，服务器端的响应的发送要根据请求被接收的顺序排队</code>，也就是说，先接收到的请求的响应也要先发送。这样造成的问题是，如果最先收到的请求的处理时间长的话，响应生成也慢，就会阻塞已经生成了的响应的发送。也会造成队头阻塞。<br>可见，http1.1 的队首阻塞发生在服务器端。</p>
<p>如果用图来表示的话，过程大概是：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji30r665j31210d83zr.jpg" alt></p>
<p><code>HTTP/2</code> 和 <code>HTTP/1.1</code>:</p>
<p>为了解决<code>HTTP/1.1</code>中的服务端队首阻塞，<code>HTTP/2</code>采用了<code>二进制分帧</code> 和 <code>多路复用</code> 等方法。<br><code>二进制分帧</code>中，帧是<code>HTTP/2</code>数据通信的最小单位。在<code>HTTP/1.1</code>数据包是文本格式，而<code>HTTP/2</code>的数据包是二进制格式的，也就是二进制帧。采用帧可以将请求和响应的数据分割得更小，且二进制协议可以更高效解析。<code>HTTP/2</code>中，同域名下所有通信都在单个连接上完成，该连接可以承载任意数量的双向数据流。每个数据流都以消息的形式发送，而消息又由一个或多个帧组成。多个帧之间可以乱序发送，根据帧首部的流标识可以重新组装。<br><code>多路复用</code>用以替代原来的序列和拥塞机制。在<code>HTTP/1.1</code>中，并发多个请求需要多个 TCP 链接，且单个域名有 6-8 个 TCP 链接请求限制。在<code>HHTP/2</code>中，同一域名下的所有通信在单个链接完成，仅占用一个 TCP 链接，且在这一个链接上可以并行请求和响应，互不干扰。</p>
<blockquote>
<p><a href="https://http2.akamai.com/demo" target="_blank" rel="noopener">此网站</a>可以直观感受<code>HTTP/1.1</code>和<code>HTTP/2</code>的性能对比。</p>
</blockquote>
<h3 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h3><p>栈也是一种受限的序列，它只能够操作栈顶，不管入栈还是出栈，都是在栈顶操作。</p>
<p>在计算机科学中, 一个 栈(stack) 是一种抽象数据类型,用作表示元素的集合,具有两种主要操作:</p>
<p>push, 添加元素到栈的顶端(末尾);<br>pop, 移除栈最顶端(末尾)的元素.<br>以上两种操作可以简单概括为“后进先出(LIFO = last in, first out)”。</p>
<p>此外,应有一个 peek 操作用于访问栈当前顶端(末尾)的元素。（只返回不弹出）</p>
<blockquote>
<p>“栈”这个名称,可类比于一组物体的堆叠(一摞书,一摞盘子之类的)。</p>
</blockquote>
<p>栈的 push 和 pop 操作的示意:</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji3d1m8oj30lh0f074v.jpg" alt></p>
<p>(图片来自 <a href="https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/stack/README.zh-CN.md" target="_blank" rel="noopener">https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/stack/README.zh-CN.md</a>)</p>
<p>栈在很多地方都有着应用，比如大家熟悉的浏览器就有很多栈，其实浏览器的执行栈就是一个基本的栈结构，从数据结构上说，它就是一个栈。<br>这也就解释了，我们用递归的解法和用循环+栈的解法本质上是差不多。</p>
<p>比如如下 JS 代码：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bar</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> a = <span class="number">1</span>;</span><br><span class="line">  <span class="keyword">const</span> b = <span class="number">2</span>;</span><br><span class="line">  <span class="built_in">console</span>.log(a, b);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">foo</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> a = <span class="number">1</span>;</span><br><span class="line">  bar();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">foo();</span><br></pre></td></tr></table></figure>

<p>真正执行的时候，内部大概是这样的：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji3jo8ozj30v70hi0u8.jpg" alt></p>
<blockquote>
<p>我画的图没有画出执行上下文中其他部分（this 和 scope 等）， 这部分是闭包的关键，而我这里不是将闭包的，是为了讲解栈的。</p>
</blockquote>
<blockquote>
<p>社区中有很多“执行上下文中的 scope 指的是执行栈中父级声明的变量”说法，这是完全错误的， JS 是词法作用域，scope 指的是函数定义时候的父级，和执行没关系</p>
</blockquote>
<p>栈常见的应用有进制转换，括号匹配，栈混洗，中缀表达式（用的很少），后缀表达式（逆波兰表达式）等。</p>
<blockquote>
<p>合法的栈混洗操作，其实和合法的括号匹配表达式之间存在着一一对应的关系，<br>也就是说 n 个元素的栈混洗有多少种，n 对括号的合法表达式就有多少种。感兴趣的可以查找相关资料</p>
</blockquote>
<h3 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h3><p>链表是一种最基本数据结构，熟练掌握链表的结构和常见操作是基础中的基础。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji3xxu0kj30bm01lglg.jpg" alt></p>
<p>(图片来自： <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/linked-list/traversal" target="_blank" rel="noopener">https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/linked-list/traversal</a>)</p>
<h4 id="React-Fiber"><a href="#React-Fiber" class="headerlink" title="React Fiber"></a>React Fiber</h4><p>很多人都说 fiber 是基于链表实现的，但是为什么要基于链表呢，可能很多人并没有答案，那么我觉得可以把这两个点（fiber 和链表）放到一起来讲下。</p>
<p>fiber 出现的目的其实是为了解决 react 在执行的时候是无法停下来的，需要一口气执行完的问题的。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji494wa9j30rc0c0wez.jpg" alt></p>
<p>图片来自 Lin Clark 在 ReactConf 2017 分享</p>
<p>上面已经指出了引入 fiber 之前的问题，就是 react 会阻止优先级高的代码（比如用户输入）执行。因此 fiber<br>打算自己自建一个<code>虚拟执行栈</code>来解决这个问题，这个虚拟执行栈的实现是链表。</p>
<p>Fiber 的基本原理是将协调过程分成小块，一次执行一块，然乎将运算结果保存起来，并判断是否有时间（react 自己实现了一个类似 requestIdleCallback 的功能）继续执行下一块。<br>如果有时间，则继续。 否则跳出，让浏览器主线程歇一会，执行别的优先级高的代码。</p>
<p>当协调过程完成（所有的小块都运算完毕）， 那么就会进入提交阶段， 真正的进行副作用（side effect）操作，比如更新 DOM，这个过程是没有办法取消的，原因就是这部分有副作用。</p>
<p>问题的关键就是将协调的过程划分为一块块的，最后还可以合并到一起，有点像 Map／Reduce。</p>
<p>React 必须重新实现遍历树的算法，从依赖于<code>内置堆栈的同步递归模型</code>，变为<code>具有链表和指针的异步模型</code>。</p>
<blockquote>
<p>Andrew 是这么说的： 如果你只依赖于[内置]调用堆栈，它将继续工作直到堆栈为空。。。</p>
</blockquote>
<p>如果我们可以随意中断调用堆栈并手动操作堆栈帧，那不是很好吗？<br>这就是 React Fiber 的目的。 <code>Fiber 是堆栈的重新实现，专门用于 React 组件</code>。 你可以将单个 Fiber 视为一个<code>虚拟堆栈帧</code>。</p>
<p>react fiber 大概是这样的：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> fiber = &#123;</span><br><span class="line">  tag: HOST_COMPONENT,</span><br><span class="line">  type: <span class="string">"div"</span>,</span><br><span class="line">  <span class="keyword">return</span>: parentFiber,</span><br><span class="line">  children: childFiber,</span><br><span class="line">  sibling: childFiber,</span><br><span class="line">  alternate: currentFiber,</span><br><span class="line">  stateNode: <span class="built_in">document</span>.createElement(<span class="string">"div"</span>),</span><br><span class="line">  props: &#123; <span class="attr">children</span>: [], <span class="attr">className</span>: <span class="string">"foo"</span> &#125;,</span><br><span class="line">  partialState: <span class="literal">null</span>,</span><br><span class="line">  effectTag: PLACEMENT,</span><br><span class="line">  effects: []</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>从这里可以看出 fiber 本质上是个对象，使用 parent，child，sibling 属性去构建 fiber 树来表示组件的结构树，<br>return, children, sibling 也都是一个 fiber，因此 fiber 看起来就是一个链表。</p>
<blockquote>
<p>细心的朋友可能已经发现了， alternate 也是一个 fiber， 那么它是用来做什么的呢？<br>它其实原理有点像 git， 可以用来执行 git revert ,git commit 等操作，这部分挺有意思，我会在我的《从零开发 git》中讲解</p>
</blockquote>
<p>想要了解更多的朋友可以看<a href="https://github.com/dawn-plex/translate/blob/master/articles/the-how-and-why-on-reacts-usage-of-linked-list-in-fiber-to-walk-the-components-tree.md" target="_blank" rel="noopener">这个文章</a></p>
<p>如果可以翻墙， 可以看<a href="https://medium.com/react-in-depth/the-how-and-why-on-reacts-usage-of-linked-list-in-fiber-67f1014d0eb7" target="_blank" rel="noopener">英文原文</a></p>
<p><a href="https://engineering.hexacta.com/didact-fiber-incremental-reconciliation-b2fe028dcaec" target="_blank" rel="noopener">这篇文章</a>也是早期讲述 fiber 架构的优秀文章</p>
<p>我目前也在写关于《从零开发 react 系列教程》中关于 fiber 架构的部分，如果你对具体实现感兴趣，欢迎关注。</p>
<h2 id="非线性结构"><a href="#非线性结构" class="headerlink" title="非线性结构"></a>非线性结构</h2><p>那么有了线性结构，我们为什么还需要非线性结构呢？ 答案是为了高效地兼顾静态操作和动态操作。大家可以对照各种数据结构的各种操作的复杂度来直观感受一下。</p>
<h3 id="树"><a href="#树" class="headerlink" title="树"></a>树</h3><p>树的应用同样非常广泛，小到文件系统，大到因特网，组织架构等都可以表示为树结构，而在我们前端眼中比较熟悉的 DOM 树也是一种树结构，而 HTML 作为一种 DSL 去描述这种树结构的具体表现形式。如果你接触过 AST，那么 AST 也是一种树，XML 也是树结构。。。树的应用远比大多数人想象的要得多。</p>
<p>树其实是一种特殊的<code>图</code>，是一种无环连通图，是一种极大无环图，也是一种极小连通图。</p>
<p>从另一个角度看，树是一种递归的数据结构。而且树的不同表示方法，比如不常用的<code>长子 + 兄弟</code>法，对于<br>你理解树这种数据结构有着很大用处， 说是一种对树的本质的更深刻的理解也不为过。</p>
<p>树的基本算法有前中后序遍历和层次遍历，有的同学对前中后这三个分别具体表现的访问顺序比较模糊，其实当初我也是一样的，后面我学到了一点，你只需要记住：<code>所谓的前中后指的是根节点的位置，其他位置按照先左后右排列即可</code>。比如前序遍历就是<code>根左右</code>, 中序就是<code>左根右</code>，后序就是<code>左右根</code>， 很简单吧？</p>
<p>我刚才提到了树是一种递归的数据结构，因此树的遍历算法使用递归去完成非常简单，幸运的是树的算法基本上都要依赖于树的遍历。 但是递归在计算机中的性能一直都有问题，因此掌握不那么容易理解的”命令式地迭代”遍历算法在某些情况下是有用的。如果你使用迭代式方式去遍历的话，可以借助上面提到的<code>栈</code>来进行，可以极大减少代码量。</p>
<blockquote>
<p>如果使用栈来简化运算，由于栈是 FILO 的，因此一定要注意左右子树的推入顺序。</p>
</blockquote>
<p>树的重要性质：</p>
<ul>
<li>如果树有 n 个顶点，那么其就有 n - 1 条边，这说明了树的顶点数和边数是同阶的。</li>
<li>任何一个节点到根节点存在<code>唯一</code>路径, 路径的长度为节点所处的深度</li>
</ul>
<p>实际使用的树有可能会更复杂，比如使用在游戏中的碰撞检测可能会用到四叉树或者八叉树。以及 k 维的树结构 <code>k-d 树</code>等。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gajhqov8pjj306y06mweo.jpg" alt><br>（图片来自 <a href="https://zh.wikipedia.org/wiki/K-d%E6%A0%91）" target="_blank" rel="noopener">https://zh.wikipedia.org/wiki/K-d%E6%A0%91）</a></p>
<h4 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h4><p>二叉树是节点度数不超过二的树，是树的一种特殊子集，有趣的是二叉树这种被限制的树结构却能够表示和实现所有的树，<br>它背后的原理正是<code>长子 + 兄弟</code>法，用邓老师的话说就是<code>二叉树是多叉树的特例，但在有根且有序时，其描述能力却足以覆盖后者</code>。</p>
<blockquote>
<p>实际上， 在你使用<code>长子 + 兄弟</code>法表示树的同时，进行 45 度角旋转即可。</p>
</blockquote>
<p>一个典型的二叉树：</p>
<p>标记为 7 的节点具有两个子节点, 标记为 2 和 6; 一个父节点,标记为 2,作为根节点, 在顶部,没有父节点。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwly1gaji4vav1hj308m07baa6.jpg" alt></p>
<p>(图片来自 <a href="https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/tree/README.zh-CN.md" target="_blank" rel="noopener">https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/tree/README.zh-CN.md</a>)</p>
<p>对于一般的树，我们通常会去遍历，这里又会有很多变种。</p>
<p>下面我列举一些二叉树遍历的相关算法:</p>
<ul>
<li><a href="../problems/94.binary-tree-inorder-traversal.md">94.binary-tree-inorder-traversal</a></li>
<li><a href="../problems/102.binary-tree-level-order-traversal.md">102.binary-tree-level-order-traversal</a></li>
<li><a href="../problems/103.binary-tree-zigzag-level-order-traversal.md">103.binary-tree-zigzag-level-order-traversal</a></li>
<li><a href="../problems/144.binary-tree-preorder-traversal.md">144.binary-tree-preorder-traversal</a></li>
<li><a href="../problems/145.binary-tree-postorder-traversal.md">145.binary-tree-postorder-traversal</a></li>
<li><a href="../problems/199.binary-tree-right-side-view.md">199.binary-tree-right-side-view</a></li>
</ul>
<p>相关概念：</p>
<ul>
<li>真二叉树 （所有节点的度数只能是偶数，即只能为 0 或者 2）</li>
</ul>
<p>另外我也专门开设了<a href="./binary-tree-traversal.md">二叉树的遍历</a>章节, 具体细节和算法可以去那里查看。</p>
<h5 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h5><p>堆其实是一种优先级队列，在很多语言都有对应的内置数据结构，很遗憾 javascript 没有这种原生的数据结构。<br>不过这对我们理解和运用不会有影响。</p>
<p>堆的特点：</p>
<ul>
<li>在一个 最小堆(min heap) 中, 如果 P 是 C 的一个父级节点, 那么 P 的 key(或 value)应小于或等于 C 的对应值.<br>正因为此，堆顶元素一定是最小的，我们会利用这个特点求最小值或者第 k 小的值。</li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji593urzj30ca07yjro.jpg" alt></p>
<ul>
<li>在一个 最大堆(max heap) 中, P 的 key(或 value)大于 C 的对应值。</li>
</ul>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwly1gaji5rurzpj30ct0abgm4.jpg" alt></p>
<p>需要注意的是优先队列不仅有堆一种，还有更复杂的，但是通常来说，我们会把两者做等价。</p>
<p>相关算法：</p>
<ul>
<li><a href="../problems/295.find-median-from-data-stream.md">295.find-median-from-data-stream</a></li>
</ul>
<h5 id="二叉查找树"><a href="#二叉查找树" class="headerlink" title="二叉查找树"></a>二叉查找树</h5><p>二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。</p>
<p>二叉查找树具有下列性质的二叉树：</p>
<ul>
<li>若左子树不空，则左子树上所有节点的值均小于它的根节点的值；</li>
<li>若右子树不空，则右子树上所有节点的值均大于它的根节点的值；</li>
<li>左、右子树也分别为二叉排序树；</li>
<li>没有键值相等的节点。</li>
</ul>
<p>对于一个二叉查找树，常规操作有插入，查找，删除，找父节点，求最大值，求最小值。</p>
<p>二叉查找树，之所以叫查找树就是因为其非常适合查找，举个例子，<br>如下一颗二叉查找树，我们想找节点值小于且最接近 58 的节点，搜索的流程如图所示：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwgy1gaji6etgvwj30rs0mudhi.jpg" alt><br>（图片来自 <a href="https://www.geeksforgeeks.org/floor-in-binary-search-tree-bst/）" target="_blank" rel="noopener">https://www.geeksforgeeks.org/floor-in-binary-search-tree-bst/）</a></p>
<p>另外我们二叉查找树有一个性质是： <code>其中序遍历的结果是一个有序数组</code>。<br>有时候我们可以利用到这个性质。</p>
<p>相关题目：</p>
<ul>
<li><a href="../problems/98.validate-binary-search-tree.md">98.validate-binary-search-tree</a></li>
</ul>
<h5 id="二叉平衡树"><a href="#二叉平衡树" class="headerlink" title="二叉平衡树"></a>二叉平衡树</h5><p>平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。</p>
<p>在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。</p>
<p>一些数据库引擎内部就是用的这种数据结构，其目标也是将查询的操作降低到 logn（树的深度），可以简单理解为<code>树在数据结构层面构造了二分查找算法</code>。</p>
<p>基本操作：</p>
<ul>
<li><p>旋转</p>
</li>
<li><p>插入</p>
</li>
<li><p>删除</p>
</li>
<li><p>查询前驱</p>
</li>
<li><p>查询后继</p>
</li>
</ul>
<h6 id="AVL"><a href="#AVL" class="headerlink" title="AVL"></a>AVL</h6><p>是最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 {\displaystyle O(\log {n})} O(\log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在 1962 年的论文 An algorithm for the organization of information 中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。</p>
<h6 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h6><p>在 1972 年由鲁道夫·贝尔发明，被称为”对称二叉 B 树”，它现代的名字源于 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 {\displaystyle O(\log {n})} O(\log{n})时间内完成查找，插入和删除，这里的 n 是树中元素的数目</p>
<h4 id="字典树-前缀树"><a href="#字典树-前缀树" class="headerlink" title="字典树(前缀树)"></a>字典树(前缀树)</h4><p>又称 Trie 树，是一种树形结构。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwly1gajj0g78e6j30al06qwfc.jpg" alt></p>
<p>(图来自 <a href="https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin" target="_blank" rel="noopener">https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin</a>)<br>它有 3 个基本性质：</p>
<ul>
<li>根节点不包含字符，除根节点外每一个节点都只包含一个字符；</li>
<li>从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；</li>
<li>每个节点的所有子节点包含的字符都不相同。</li>
</ul>
<h5 id="immutable-与-字典树"><a href="#immutable-与-字典树" class="headerlink" title="immutable 与 字典树"></a>immutable 与 字典树</h5><p><code>immutableJS</code>的底层就是<code>share + tree</code>. 这样看的话，其实和字典树是一致的。</p>
<p>相关算法：</p>
<ul>
<li><a href="../problems/208.implement-trie-prefix-tree.md">208.implement-trie-prefix-tree</a></li>
</ul>
<h3 id="图"><a href="#图" class="headerlink" title="图"></a>图</h3><p>前面讲的数据结构都可以看成是图的特例。 前面提到了二叉树完全可以实现其他树结构，<br>其实有向图也完全可以实现无向图和混合图，因此有向图的研究一直是重点考察对象。</p>
<p>图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。</p>
<h4 id="图的表示方法"><a href="#图的表示方法" class="headerlink" title="图的表示方法"></a>图的表示方法</h4><ul>
<li>邻接矩阵(常见)</li>
</ul>
<p>空间复杂度 O(n^2),n 为顶点个数。</p>
<p>优点：</p>
<ol>
<li><p>直观，简单。</p>
</li>
<li><p>适用于稠密图</p>
</li>
<li><p>判断两个顶点是否连接，获取入度和出度以及更新度数，时间复杂度都是 O(1)</p>
</li>
</ol>
<ul>
<li>关联矩阵</li>
<li>邻接表</li>
</ul>
<p>对于每个点，存储着一个链表，用来指向所有与该点直接相连的点<br>对于有权图来说，链表中元素值对应着权重</p>
<p>例如在无向无权图中：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwly1gaji793gchj30k00akq48.jpg" alt><br>（图片来自 <a href="https://zhuanlan.zhihu.com/p/25498681）" target="_blank" rel="noopener">https://zhuanlan.zhihu.com/p/25498681）</a></p>
<p>可以看出在无向图中，邻接矩阵关于对角线对称，而邻接链表总有两条对称的边<br>而在有向无权图中：</p>
<p><img src="https://tva1.sinaimg.cn/large/006tNbRwly1gaji7giyerj30k00aq0ux.jpg" alt></p>
<p>（图片来自 <a href="https://zhuanlan.zhihu.com/p/25498681）" target="_blank" rel="noopener">https://zhuanlan.zhihu.com/p/25498681）</a></p>
<h4 id="图的遍历"><a href="#图的遍历" class="headerlink" title="图的遍历"></a>图的遍历</h4><p>图的遍历就是要找出图中所有的点，一般有以下两种方法：</p>
<ol>
<li>深度优先遍历：(Depth First Search, DFS)</li>
</ol>
<p>深度优先遍历图的方法是，从图中某顶点 v 出发， 不断访问邻居， 邻居的邻居直到访问完毕。</p>
<ol start="2">
<li>广度优先搜索：(Breadth First Search, BFS)</li>
</ol>
<p>广度优先搜索，可以被形象地描述为 “浅尝辄止”，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。</p>

      </div>
      
        <br>
        


  <section class='meta' id="footer-meta">
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2020-01-14T09:56:11+08:00">
  <a class='notlink'>
    <i class="fas fa-clock" aria-hidden="true"></i>
    <p>更新于 2020年1月14日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/blog/tags/数据结构/" rel="nofollow"><i class="fas fa-tag" aria-hidden="true"></i><p>数据结构</p></a></div>


        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class='qrcode' rel="external nofollow noopener noreferrer" href=''>
        
          <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qrcode.png">
        
        </a>
      
    
      
        <a class="-mob-share-qq" title="QQ好友" rel="external nofollow noopener noreferrer"
          
          href="http://connect.qq.com/widget/shareqq/index.html?url=https://lucifer.ren/blog/2020/01/03/basic-data-structure/&title=数据结构快速盘点 | lucifer的网络博客&pics=https://avatars0.githubusercontent.com/u/12479470?s=400&u=442571e44cbd0b67e3503e9551d4445c78f593f8&v=4&summary=这篇文章不是讲解数据结构的文章，而是结合现实的场景帮助大家理解和复习数据结构与算法，如果你的数据结构基础很差，建议先去看一些基础教程，再转过来看。
本篇文章的定位是侧重于前端的，通过学习前端中实际场景的数据结构，从而加深大家对数据结构的理解和认识。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qq.png">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="QQ空间" rel="external nofollow noopener noreferrer"
          
          href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://lucifer.ren/blog/2020/01/03/basic-data-structure/&title=数据结构快速盘点 | lucifer的网络博客&pics=https://avatars0.githubusercontent.com/u/12479470?s=400&u=442571e44cbd0b67e3503e9551d4445c78f593f8&v=4&summary=这篇文章不是讲解数据结构的文章，而是结合现实的场景帮助大家理解和复习数据结构与算法，如果你的数据结构基础很差，建议先去看一些基础教程，再转过来看。
本篇文章的定位是侧重于前端的，通过学习前端中实际场景的数据结构，从而加深大家对数据结构的理解和认识。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qzone.png">
          
        </a>
      
    
      
        <a class="-mob-share-weibo" title="微博" rel="external nofollow noopener noreferrer"
          
          href="http://service.weibo.com/share/share.php?url=https://lucifer.ren/blog/2020/01/03/basic-data-structure/&title=数据结构快速盘点 | lucifer的网络博客&pics=https://avatars0.githubusercontent.com/u/12479470?s=400&u=442571e44cbd0b67e3503e9551d4445c78f593f8&v=4&summary=这篇文章不是讲解数据结构的文章，而是结合现实的场景帮助大家理解和复习数据结构与算法，如果你的数据结构基础很差，建议先去看一些基础教程，再转过来看。
本篇文章的定位是侧重于前端的，通过学习前端中实际场景的数据结构，从而加深大家对数据结构的理解和认识。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/weibo.png">
          
        </a>
      
    
  </div>
</div>



        
      
    </div>
  </section>


      
      
          <div class="prev-next">
              
                  <section class="prev">
                      <span class="art-item-left">
                          <h6><i class="fas fa-chevron-left" aria-hidden="true"></i>&nbsp;上一页</h6>
                          <h4>
                              <a href="/blog/2020/01/09/1310.xor-queries-of-a-subarray/" rel="prev" title="掌握前缀表达式真的可以为所欲为！">
                                
                                    掌握前缀表达式真的可以为所欲为！
                                
                              </a>
                          </h4>
                          
                              
                              <h6 class="tags">
                                  <a class="tag" href="/blog/tags/数据结构/"><i class="fas fa-tag fa-fw" aria-hidden="true"></i> 数据结构</a> <a class="tag" href="/blog/tags/算法/"><i class="fas fa-tag fa-fw" aria-hidden="true"></i> 算法</a> <a class="tag" href="/blog/tags/前缀和/"><i class="fas fa-tag fa-fw" aria-hidden="true"></i> 前缀和</a> <a class="tag" href="/blog/tags/前缀表达式/"><i class="fas fa-tag fa-fw" aria-hidden="true"></i> 前缀表达式</a>
                              </h6>
                          
                      </span>
                  </section>
              
              
                  <section class="next">
                      <span class="art-item-right" aria-hidden="true">
                          <h6>下一页&nbsp;<i class="fas fa-chevron-right" aria-hidden="true"></i></h6>
                          <h4>
                              <a href="/blog/2020/01/01/daily-featured-2019-12/" rel="prev" title="每日一荐 2019-12 汇总">
                                  
                                      每日一荐 2019-12 汇总
                                  
                              </a>
                          </h4>
                          
                              
                              <h6 class="tags">
                                  <a class="tag" href="/blog/tags/每日一荐/"><i class="fas fa-tag fa-fw" aria-hidden="true"></i> 每日一荐</a>
                              </h6>
                          
                      </span>
                  </section>
              
          </div>
      
    </section>
  </article>



  <!-- 显示推荐文章和评论 -->



  <article class="post white-box comments">
    <section class="article typo">
      <h4><i class="fas fa-comments fa-fw" aria-hidden="true"></i>&nbsp;评论</h4>
      
      
      
        <section id="comments">
          <div id="gitalk-container"></div>
        </section>
      
      
    </section>
  </article>






<!-- 根据页面mathjax变量决定是否加载MathJax数学公式js -->



  <script>
    window.subData = {
      title: '数据结构快速盘点',
      tools: true
    }
  </script>


</div>
<aside class='l_side'>
  
    
    
      
      
        
          
          
            
              <section class='widget author'>
  <div class='content pure'>
    
    
    
      <div class="social-wrapper">
        
          
            <a href="/blog/atom.xml"
              class="social fas fa-rss flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://www.zhihu.com/people/lu-xiao-13-70/activities"
              class="social fab fa-zhihu flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="mailto:azl397985856@gmail.com"
              class="social fas fa-envelope flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://github.com/azl397985856"
              class="social fab fa-github flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://music.163.com/playlist?id=978545815&userid=632167080"
              class="social fas fa-headphones-alt flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
      </div>
    
  </div>
</section>

            
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
      
        
          
          
        
          
          
            
              
  <section class='widget toc-wrapper'>
    
<header class='pure'>
  <div><i class="fas fa-list fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;本文目录</div>
  
    <!-- <div class='wrapper'><a class="s-toc rightBtn" rel="external nofollow noopener noreferrer" href="javascript:void(0)"><i class="fas fa-thumbtack fa-fw"></i></a></div> -->
  
</header>

    <div class='content pure'>
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#线性结构"><span class="toc-text">线性结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#数组"><span class="toc-text">数组</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#React-Hooks"><span class="toc-text">React Hooks</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#队列"><span class="toc-text">队列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#栈"><span class="toc-text">栈</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#链表"><span class="toc-text">链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#React-Fiber"><span class="toc-text">React Fiber</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#非线性结构"><span class="toc-text">非线性结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#树"><span class="toc-text">树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#二叉树"><span class="toc-text">二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#堆"><span class="toc-text">堆</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#二叉查找树"><span class="toc-text">二叉查找树</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#二叉平衡树"><span class="toc-text">二叉平衡树</span></a><ol class="toc-child"><li class="toc-item toc-level-6"><a class="toc-link" href="#AVL"><span class="toc-text">AVL</span></a></li><li class="toc-item toc-level-6"><a class="toc-link" href="#红黑树"><span class="toc-text">红黑树</span></a></li></ol></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#字典树-前缀树"><span class="toc-text">字典树(前缀树)</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#immutable-与-字典树"><span class="toc-text">immutable 与 字典树</span></a></li></ol></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#图"><span class="toc-text">图</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#图的表示方法"><span class="toc-text">图的表示方法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#图的遍历"><span class="toc-text">图的遍历</span></a></li></ol></li></ol></li></ol>
    </div>
  </section>


            
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
      
        
          
          
        
          
          
        
          
          
            
              <section class='widget grid'>
  
<header class='pure'>
  <div><i class="fas fa-map-signs fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;我的开源项目</div>
  
</header>

  <div class='content pure'>
    <ul class="grid navgation">
      
        <li><a class="flat-box" title="https://github.com/azl397985856/leetcode" href="https://github.com/azl397985856/leetcode"
          
          
          id="https:github.comazl397985856leetcode">
          
            <i class="fab fa-github fa-fw" aria-hidden="true"></i>
          
          LeetCode
        </a></li>
      
        <li><a class="flat-box" title="https://github.com/azl397985856/fe-interview" href="https://github.com/azl397985856/fe-interview"
          
          
          id="https:github.comazl397985856fe-interview">
          
            <i class="fab fa-github fa-fw" aria-hidden="true"></i>
          
          大前端
        </a></li>
      
        <li><a class="flat-box" title="https://github.com/azl397985856/daily-featured" href="https://github.com/azl397985856/daily-featured"
          
          
          id="https:github.comazl397985856daily-featured">
          
            <i class="fab fa-github fa-fw" aria-hidden="true"></i>
          
          每日一荐
        </a></li>
      
    </ul>
  </div>
</section>

            
          
        
          
          
        
          
          
        
          
          
        
          
          
        
      
        
          
          
        
          
          
        
          
          
        
          
          
            
              
  <section class='widget category'>
    
<header class='pure'>
  <div><i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;全部分类</div>
  
    <a class="rightBtn"
    
      rel="external nofollow noopener noreferrer"
    
    
    href="/blog/categories/"
    title="categories/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <ul class="entry">
        
          <li><a class="flat-box" title="/blog/categories/91天学算法/" href="/blog/categories/91天学算法/"><div class='name'>91天学算法</div><div class='badge'>(4)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/Easy/" href="/blog/categories/Easy/"><div class='name'>Easy</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/Hard/" href="/blog/categories/Hard/"><div class='name'>Hard</div><div class='badge'>(3)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/LeetCode/" href="/blog/categories/LeetCode/"><div class='name'>LeetCode</div><div class='badge'>(15)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/LeetCode/LeetCode题解书/" href="/blog/categories/LeetCode/LeetCode题解书/"><div class='name'>LeetCode题解书</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/LeetCode/动态规划/" href="/blog/categories/LeetCode/动态规划/"><div class='name'>动态规划</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/Medium/" href="/blog/categories/Medium/"><div class='name'>Medium</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/React/" href="/blog/categories/React/"><div class='name'>React</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/TypeScript/" href="/blog/categories/TypeScript/"><div class='name'>TypeScript</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/中等/" href="/blog/categories/中等/"><div class='name'>中等</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/书/" href="/blog/categories/书/"><div class='name'>书</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/书/算法/" href="/blog/categories/书/算法/"><div class='name'>算法</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/书摘/" href="/blog/categories/书摘/"><div class='name'>书摘</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/二叉树/" href="/blog/categories/二叉树/"><div class='name'>二叉树</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/前端/" href="/blog/categories/前端/"><div class='name'>前端</div><div class='badge'>(14)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/TypeScript/" href="/blog/categories/前端/TypeScript/"><div class='name'>TypeScript</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/TypeScript/泛型/" href="/blog/categories/前端/TypeScript/泛型/"><div class='name'>泛型</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/eslint/" href="/blog/categories/前端/eslint/"><div class='name'>eslint</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/web-component/" href="/blog/categories/前端/web-component/"><div class='name'>web-component</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/测试/" href="/blog/categories/前端/测试/"><div class='name'>测试</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/浏览器/" href="/blog/categories/前端/浏览器/"><div class='name'>浏览器</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/算法/" href="/blog/categories/前端/算法/"><div class='name'>算法</div><div class='badge'>(4)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/前端/组件化/" href="/blog/categories/前端/组件化/"><div class='name'>组件化</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/力扣加加/" href="/blog/categories/力扣加加/"><div class='name'>力扣加加</div><div class='badge'>(5)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/学习方法/" href="/blog/categories/学习方法/"><div class='name'>学习方法</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/异议！/" href="/blog/categories/异议！/"><div class='name'>异议！</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/技术大会/" href="/blog/categories/技术大会/"><div class='name'>技术大会</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/技术大会/D2/" href="/blog/categories/技术大会/D2/"><div class='name'>D2</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/技术大会/Google-IO/" href="/blog/categories/技术大会/Google-IO/"><div class='name'>Google IO</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/技术大会/JSConf/" href="/blog/categories/技术大会/JSConf/"><div class='name'>JSConf</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/技术大会/QCon/" href="/blog/categories/技术大会/QCon/"><div class='name'>QCon</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/技术大会/React-Conf/" href="/blog/categories/技术大会/React-Conf/"><div class='name'>React Conf</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/数据结构/" href="/blog/categories/数据结构/"><div class='name'>数据结构</div><div class='badge'>(23)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/hashtable/" href="/blog/categories/数据结构/hashtable/"><div class='name'>hashtable</div><div class='badge'>(6)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/二叉搜索树/" href="/blog/categories/数据结构/二叉搜索树/"><div class='name'>二叉搜索树</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/图/" href="/blog/categories/数据结构/图/"><div class='name'>图</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/字符串/" href="/blog/categories/数据结构/字符串/"><div class='name'>字符串</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/平衡二叉树/" href="/blog/categories/数据结构/平衡二叉树/"><div class='name'>平衡二叉树</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/数组/" href="/blog/categories/数据结构/数组/"><div class='name'>数组</div><div class='badge'>(6)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/算法/" href="/blog/categories/数据结构/算法/"><div class='name'>算法</div><div class='badge'>(5)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/数据结构/链表/" href="/blog/categories/数据结构/链表/"><div class='name'>链表</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/数据结构，二叉树/" href="/blog/categories/数据结构，二叉树/"><div class='name'>数据结构，二叉树</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/数据结构，单调栈/" href="/blog/categories/数据结构，单调栈/"><div class='name'>数据结构，单调栈</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/数据结构，字符串/" href="/blog/categories/数据结构，字符串/"><div class='name'>数据结构，字符串</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/数据结构，数组/" href="/blog/categories/数据结构，数组/"><div class='name'>数据结构，数组</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/日记/" href="/blog/categories/日记/"><div class='name'>日记</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/日记/技术/" href="/blog/categories/日记/技术/"><div class='name'>技术</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/每日一荐/" href="/blog/categories/每日一荐/"><div class='name'>每日一荐</div><div class='badge'>(6)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2019-09/" href="/blog/categories/每日一荐/2019-09/"><div class='name'>2019-09</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2019-10/" href="/blog/categories/每日一荐/2019-10/"><div class='name'>2019-10</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2019-11/" href="/blog/categories/每日一荐/2019-11/"><div class='name'>2019-11</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2019-12/" href="/blog/categories/每日一荐/2019-12/"><div class='name'>2019-12</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2020-01/" href="/blog/categories/每日一荐/2020-01/"><div class='name'>2020-01</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/每日一荐/2020-03/" href="/blog/categories/每日一荐/2020-03/"><div class='name'>2020-03</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/浏览器/" href="/blog/categories/浏览器/"><div class='name'>浏览器</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/浏览器/事件/" href="/blog/categories/浏览器/事件/"><div class='name'>事件</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/电影/" href="/blog/categories/电影/"><div class='name'>电影</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/电影/观后感/" href="/blog/categories/电影/观后感/"><div class='name'>观后感</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/算法/" href="/blog/categories/算法/"><div class='name'>算法</div><div class='badge'>(20)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/BFS/" href="/blog/categories/算法/BFS/"><div class='name'>BFS</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/DFS/" href="/blog/categories/算法/DFS/"><div class='name'>DFS</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/二分法/" href="/blog/categories/算法/二分法/"><div class='name'>二分法</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/位运算/" href="/blog/categories/算法/位运算/"><div class='name'>位运算</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/前缀和/" href="/blog/categories/算法/前缀和/"><div class='name'>前缀和</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/动态规划/" href="/blog/categories/算法/动态规划/"><div class='name'>动态规划</div><div class='badge'>(4)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/双指针/" href="/blog/categories/算法/双指针/"><div class='name'>双指针</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/回文/" href="/blog/categories/算法/回文/"><div class='name'>回文</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/回溯/" href="/blog/categories/算法/回溯/"><div class='name'>回溯</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/子序列/" href="/blog/categories/算法/子序列/"><div class='name'>子序列</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/就地算法/" href="/blog/categories/算法/就地算法/"><div class='name'>就地算法</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/布隆过滤器/" href="/blog/categories/算法/布隆过滤器/"><div class='name'>布隆过滤器</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/循环移位/" href="/blog/categories/算法/循环移位/"><div class='name'>循环移位</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/数学/" href="/blog/categories/算法/数学/"><div class='name'>数学</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/概率/" href="/blog/categories/算法/概率/"><div class='name'>概率</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/母题/" href="/blog/categories/算法/母题/"><div class='name'>母题</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/状态压缩/" href="/blog/categories/算法/状态压缩/"><div class='name'>状态压缩</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/背包问题/" href="/blog/categories/算法/背包问题/"><div class='name'>背包问题</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/递归/" href="/blog/categories/算法/递归/"><div class='name'>递归</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box child" title="/blog/categories/算法/链表反转/" href="/blog/categories/算法/链表反转/"><div class='name'>链表反转</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/算法，动态规划/" href="/blog/categories/算法，动态规划/"><div class='name'>算法，动态规划</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/算法，序列化/" href="/blog/categories/算法，序列化/"><div class='name'>算法，序列化</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/算法，滑动窗口/" href="/blog/categories/算法，滑动窗口/"><div class='name'>算法，滑动窗口</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/经验分享/" href="/blog/categories/经验分享/"><div class='name'>经验分享</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/编程之美/" href="/blog/categories/编程之美/"><div class='name'>编程之美</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/解题模板/" href="/blog/categories/解题模板/"><div class='name'>解题模板</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/blog/categories/贪婪/" href="/blog/categories/贪婪/"><div class='name'>贪婪</div><div class='badge'>(1)</div></a></li>
        
      </ul>
    </div>
  </section>


            
          
        
          
          
        
          
          
        
          
          
        
      
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
            
              
  <section class='widget tagcloud'>
    
<header class='pure'>
  <div><i class="fas fa-tags fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;热门标签</div>
  
    <a class="rightBtn"
    
      rel="external nofollow noopener noreferrer"
    
    
    href="/blog/tags/"
    title="tags/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <a href="/blog/tags/91天学算法/" style="font-size: 17px; color: #858585">91天学算法</a> <a href="/blog/tags/BFS/" style="font-size: 14px; color: #999">BFS</a> <a href="/blog/tags/BigPipe/" style="font-size: 14px; color: #999">BigPipe</a> <a href="/blog/tags/Canvas/" style="font-size: 14px; color: #999">Canvas</a> <a href="/blog/tags/Chrome/" style="font-size: 14px; color: #999">Chrome</a> <a href="/blog/tags/D2/" style="font-size: 14px; color: #999">D2</a> <a href="/blog/tags/Easy/" style="font-size: 14px; color: #999">Easy</a> <a href="/blog/tags/Floyd-Warshall/" style="font-size: 14px; color: #999">Floyd-Warshall</a> <a href="/blog/tags/Google-IO/" style="font-size: 14px; color: #999">Google IO</a> <a href="/blog/tags/Hard/" style="font-size: 14px; color: #999">Hard</a> <a href="/blog/tags/JSConf/" style="font-size: 14px; color: #999">JSConf</a> <a href="/blog/tags/LeetCode/" style="font-size: 22px; color: #636363">LeetCode</a> <a href="/blog/tags/LeetCode日记/" style="font-size: 20px; color: #707070">LeetCode日记</a> <a href="/blog/tags/Mac/" style="font-size: 14px; color: #999">Mac</a> <a href="/blog/tags/Medium/" style="font-size: 15px; color: #929292">Medium</a> <a href="/blog/tags/PPT/" style="font-size: 14px; color: #999">PPT</a> <a href="/blog/tags/QCon/" style="font-size: 14px; color: #999">QCon</a> <a href="/blog/tags/RFC/" style="font-size: 14px; color: #999">RFC</a> <a href="/blog/tags/React/" style="font-size: 14px; color: #999">React</a> <a href="/blog/tags/TypeScript/" style="font-size: 16px; color: #8b8b8b">TypeScript</a> <a href="/blog/tags/eslint/" style="font-size: 14px; color: #999">eslint</a> <a href="/blog/tags/immutable/" style="font-size: 14px; color: #999">immutable</a> <a href="/blog/tags/immutablejs/" style="font-size: 14px; color: #999">immutablejs</a> <a href="/blog/tags/vue/" style="font-size: 14px; color: #999">vue</a> <a href="/blog/tags/web-component/" style="font-size: 14px; color: #999">web-component</a> <a href="/blog/tags/中等/" style="font-size: 14px; color: #999">中等</a> <a href="/blog/tags/书/" style="font-size: 14px; color: #999">书</a> <a href="/blog/tags/书摘/" style="font-size: 14px; color: #999">书摘</a> <a href="/blog/tags/事件/" style="font-size: 14px; color: #999">事件</a> <a href="/blog/tags/事件循环/" style="font-size: 14px; color: #999">事件循环</a> <a href="/blog/tags/二叉树/" style="font-size: 16px; color: #8b8b8b">二叉树</a> <a href="/blog/tags/位运算/" style="font-size: 14px; color: #999">位运算</a> <a href="/blog/tags/删除-k-个字符/" style="font-size: 14px; color: #999">删除 k 个字符</a> <a href="/blog/tags/前端/" style="font-size: 21px; color: #696969">前端</a> <a href="/blog/tags/前缀和/" style="font-size: 15px; color: #929292">前缀和</a> <a href="/blog/tags/前缀表达式/" style="font-size: 14px; color: #999">前缀表达式</a> <a href="/blog/tags/力扣加加/" style="font-size: 18px; color: #7e7e7e">力扣加加</a> <a href="/blog/tags/动态规划/" style="font-size: 18px; color: #7e7e7e">动态规划</a> <a href="/blog/tags/单元测试/" style="font-size: 14px; color: #999">单元测试</a> <a href="/blog/tags/困难/" style="font-size: 14px; color: #999">困难</a> <a href="/blog/tags/图/" style="font-size: 14px; color: #999">图</a> <a href="/blog/tags/图片处理/" style="font-size: 14px; color: #999">图片处理</a> <a href="/blog/tags/字符串/" style="font-size: 14px; color: #999">字符串</a> <a href="/blog/tags/字节跳动/" style="font-size: 14px; color: #999">字节跳动</a> <a href="/blog/tags/学习方法/" style="font-size: 15px; color: #929292">学习方法</a> <a href="/blog/tags/序列化/" style="font-size: 14px; color: #999">序列化</a> <a href="/blog/tags/异常处理/" style="font-size: 14px; color: #999">异常处理</a> <a href="/blog/tags/异议！/" style="font-size: 14px; color: #999">异议！</a> <a href="/blog/tags/循环移位/" style="font-size: 14px; color: #999">循环移位</a> <a href="/blog/tags/微前端/" style="font-size: 14px; color: #999">微前端</a> <a href="/blog/tags/必备软件/" style="font-size: 14px; color: #999">必备软件</a> <a href="/blog/tags/我的书/" style="font-size: 14px; color: #999">我的书</a> <a href="/blog/tags/扩展程序/" style="font-size: 14px; color: #999">扩展程序</a> <a href="/blog/tags/技术大会/" style="font-size: 14px; color: #999">技术大会</a> <a href="/blog/tags/技术调研/" style="font-size: 14px; color: #999">技术调研</a> <a href="/blog/tags/技能/" style="font-size: 14px; color: #999">技能</a> <a href="/blog/tags/数学/" style="font-size: 15px; color: #929292">数学</a> <a href="/blog/tags/数据结构/" style="font-size: 23px; color: #5c5c5c">数据结构</a> <a href="/blog/tags/数据结构，算法，LeetCode-日记，Hard/" style="font-size: 15px; color: #929292">数据结构，算法，LeetCode 日记，Hard</a> <a href="/blog/tags/数据结构，算法，LeetCode-日记，中等/" style="font-size: 14px; color: #999">数据结构，算法，LeetCode 日记，中等</a> <a href="/blog/tags/数组/" style="font-size: 15px; color: #929292">数组</a> <a href="/blog/tags/日记/" style="font-size: 15px; color: #929292">日记</a> <a href="/blog/tags/最长上升子序列/" style="font-size: 14px; color: #999">最长上升子序列</a> <a href="/blog/tags/最长公共子序列/" style="font-size: 14px; color: #999">最长公共子序列</a> <a href="/blog/tags/概率/" style="font-size: 14px; color: #999">概率</a> <a href="/blog/tags/母题/" style="font-size: 14px; color: #999">母题</a> <a href="/blog/tags/每日一荐/" style="font-size: 19px; color: #777">每日一荐</a> <a href="/blog/tags/泛型/" style="font-size: 15px; color: #929292">泛型</a> <a href="/blog/tags/测试/" style="font-size: 14px; color: #999">测试</a> <a href="/blog/tags/浏览器/" style="font-size: 15px; color: #929292">浏览器</a> <a href="/blog/tags/滑动窗口/" style="font-size: 15px; color: #929292">滑动窗口</a> <a href="/blog/tags/滤镜/" style="font-size: 14px; color: #999">滤镜</a> <a href="/blog/tags/状态压缩/" style="font-size: 14px; color: #999">状态压缩</a> <a href="/blog/tags/状态机/" style="font-size: 14px; color: #999">状态机</a> <a href="/blog/tags/电影/" style="font-size: 15px; color: #929292">电影</a> <a href="/blog/tags/监控/" style="font-size: 14px; color: #999">监控</a> <a href="/blog/tags/算法/" style="font-size: 24px; color: #555">算法</a> <a href="/blog/tags/算法提高班/" style="font-size: 18px; color: #7e7e7e">算法提高班</a> <a href="/blog/tags/算法系列/" style="font-size: 17px; color: #858585">算法系列</a> <a href="/blog/tags/组件化/" style="font-size: 14px; color: #999">组件化</a> <a href="/blog/tags/经验分享/" style="font-size: 15px; color: #929292">经验分享</a> <a href="/blog/tags/编程之美/" style="font-size: 14px; color: #999">编程之美</a> <a href="/blog/tags/草稿/" style="font-size: 14px; color: #999">草稿</a> <a href="/blog/tags/装机/" style="font-size: 14px; color: #999">装机</a> <a href="/blog/tags/解题模板/" style="font-size: 14px; color: #999">解题模板</a> <a href="/blog/tags/贪婪/" style="font-size: 14px; color: #999">贪婪</a> <a href="/blog/tags/贪心/" style="font-size: 14px; color: #999">贪心</a> <a href="/blog/tags/递归/" style="font-size: 14px; color: #999">递归</a> <a href="/blog/tags/链表/" style="font-size: 15px; color: #929292">链表</a> <a href="/blog/tags/陷阱题/" style="font-size: 14px; color: #999">陷阱题</a>
    </div>
  </section>


            
          
        
          
          
        
          
          
        
      
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
            
              <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-thumbs-up fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;强烈推荐</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://xaoxuu.com/wiki/hexo.sh/" href="https://xaoxuu.com/wiki/hexo.sh/"
          
          
          >
          <div class='name'>
            
              <i class=" fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Hexo脚本（Mac）
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://xaoxuu.com/wiki/vim-cn.sh/" href="https://xaoxuu.com/wiki/vim-cn.sh/"
          
          
          >
          <div class='name'>
            
              <i class=" fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;图床脚本（Mac）
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://yasuotu.com" href="https://yasuotu.com"
          
          
          >
          <div class='name'>
            
              <i class=" fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;图片在线压缩
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://realfavicongenerator.net" href="https://realfavicongenerator.net"
          
          
          >
          <div class='name'>
            
              <i class=" fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;生成Favicon
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://mxclub.github.io/resume/" href="https://mxclub.github.io/resume/"
          
          
          >
          <div class='name'>
            
              <i class=" fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;简历主题
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

            
          
        
      
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
          
          
        
      
    

  
</aside>

<footer id="footer" class="clearfix">
   
  <div class="social-wrapper">
     
    <a
      href="/blog/atom.xml"
      class="social fas fa-rss flat-btn"
      target="_blank"
      rel="external nofollow noopener noreferrer"
    >
    </a>
      
    <a
      href="https://www.zhihu.com/people/lu-xiao-13-70/activities"
      class="social fab fa-zhihu flat-btn"
      target="_blank"
      rel="external nofollow noopener noreferrer"
    >
    </a>
      
    <a
      href="mailto:azl397985856@gmail.com"
      class="social fas fa-envelope flat-btn"
      target="_blank"
      rel="external nofollow noopener noreferrer"
    >
    </a>
      
    <a
      href="https://github.com/azl397985856"
      class="social fab fa-github flat-btn"
      target="_blank"
      rel="external nofollow noopener noreferrer"
    >
    </a>
      
    <a
      href="https://music.163.com/playlist?id=978545815&amp;userid=632167080"
      class="social fas fa-headphones-alt flat-btn"
      target="_blank"
      rel="external nofollow noopener noreferrer"
    >
    </a>
     
  </div>
  
  <br />
  <div><p>博客内容遵循 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
  <div>
    本站使用
    <a href="https://xaoxuu.com/wiki/material-x/" target="_blank" class="codename"
      >Material X</a
    >
    作为主题  ， 总访问量为
    <span id="busuanzi_value_site_pv"
      ><i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i
    ></span>
    次  。
  </div>

  <span id="timeDate">载入天数...</span><span id="times">载入时分秒...</span>
  <script>
    var now = new Date();
    function createtime() {
      var grt = new Date("08/10/2018 17:38:00"); //在此处修改你的建站时间，格式：月/日/年 时:分:秒
      now.setTime(now.getTime() + 250);
      days = (now - grt) / 1000 / 60 / 60 / 24;
      dnum = Math.floor(days);
      hours = (now - grt) / 1000 / 60 / 60 - 24 * dnum;
      hnum = Math.floor(hours);
      if (String(hnum).length == 1) {
        hnum = "0" + hnum;
      }
      minutes = (now - grt) / 1000 / 60 - 24 * 60 * dnum - 60 * hnum;
      mnum = Math.floor(minutes);
      if (String(mnum).length == 1) {
        mnum = "0" + mnum;
      }
      seconds =
        (now - grt) / 1000 - 24 * 60 * 60 * dnum - 60 * 60 * hnum - 60 * mnum;
      snum = Math.round(seconds);
      if (String(snum).length == 1) {
        snum = "0" + snum;
      }
      document.getElementById("timeDate").innerHTML =
        "本站已安全运行 " + dnum + " 天 ";
      document.getElementById("times").innerHTML =
        hnum + " 小时 " + mnum + " 分 " + snum + " 秒";
    }
    setInterval("createtime()", 250);
  </script>
</footer>
<script>
  setLoadingBarProgress(80);
</script>


      <script>setLoadingBarProgress(60);</script>
    </div>
    <a class="s-top fas fa-arrow-up fa-fw" href='javascript:void(0)'></a>
  </div>
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>

  <script>
    var GOOGLE_CUSTOM_SEARCH_API_KEY = "";
    var GOOGLE_CUSTOM_SEARCH_ENGINE_ID = "";
    var ALGOLIA_API_KEY = "";
    var ALGOLIA_APP_ID = "";
    var ALGOLIA_INDEX_NAME = "";
    var AZURE_SERVICE_NAME = "";
    var AZURE_INDEX_NAME = "";
    var AZURE_QUERY_KEY = "";
    var BAIDU_API_ID = "";
    var SEARCH_SERVICE = "hexo" || "hexo";
    var ROOT = "/blog/"||"/";
    if(!ROOT.endsWith('/'))ROOT += '/';
  </script>

<script src="//instant.page/1.2.2" type="module" integrity="sha384-2xV8M5griQmzyiY3CDqh1dn4z3llDVqZDqzjzcY+jCBCk/a5fXJmuZ/40JJAPeoU"></script>


  <script async src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.5/dist/scrollreveal.min.js"></script>
  <script type="text/javascript">
    $(function() {
      const $reveal = $('.reveal');
      if ($reveal.length === 0) return;
      const sr = ScrollReveal({ distance: 0 });
      sr.reveal('.reveal');
    });
  </script>


  <script src="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.js"></script>
  <script type="text/javascript">
    $(function() {
      Waves.attach('.flat-btn', ['waves-button']);
      Waves.attach('.float-btn', ['waves-button', 'waves-float']);
      Waves.attach('.float-btn-light', ['waves-button', 'waves-float', 'waves-light']);
      Waves.attach('.flat-box', ['waves-block']);
      Waves.attach('.float-box', ['waves-block', 'waves-float']);
      Waves.attach('.waves-image');
      Waves.init();
    });
  </script>


  <script async src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-busuanzi@2.3/js/busuanzi.pure.mini.js"></script>




  
  
  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery-backstretch/2.0.4/jquery.backstretch.min.js"></script>
    <script type="text/javascript">
      $(function(){
        if ('.cover') {
          $('.cover').backstretch(
          ["https://img.vim-cn.com/29/91197b04c13f512f734a76d4ac422d89dbe229.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        } else {
          $.backstretch(
          ["https://img.vim-cn.com/29/91197b04c13f512f734a76d4ac422d89dbe229.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        }
      });
    </script>
  







  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
  <script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
  <script type="text/javascript">
    var gitalk = new Gitalk({
      clientID: "aea1377036afe4cd0343",
      clientSecret: "815c638dea8644b7a4b97905707cf72b45555f6d",
      repo: "blog",
      owner: "azl397985856",
      admin: "azl397985856",
      
        id: location.pathname,      // Ensure uniqueness and length less than 50
      
      distractionFreeMode: false  // Facebook-like distraction free mode
    });
    gitalk.render('gitalk-container');
  </script>





  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.9/js/app.js"></script>


  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.9/js/search.js"></script>




<!-- 复制 -->
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  let COPY_SUCCESS = "复制成功";
  let COPY_FAILURE = "复制失败";
  /*页面载入完成后，创建复制按钮*/
  !function (e, t, a) {
    /* code */
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '  <i class="fa fa-copy"></i><span>复制</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });

      clipboard.on('success', function(e) {
        //您可以加入成功提示
        console.info('Action:', e.action);
        console.info('Text:', e.text);
        console.info('Trigger:', e.trigger);
        success_prompt(COPY_SUCCESS);
        e.clearSelection();
      });
      clipboard.on('error', function(e) {
        //您可以加入失败提示
        console.error('Action:', e.action);
        console.error('Trigger:', e.trigger);
        fail_prompt(COPY_FAILURE);
      });
    }
    initCopyCode();

  }(window, document);

  /**
   * 弹出式提示框，默认1.5秒自动消失
   * @param message 提示信息
   * @param style 提示样式，有alert-success、alert-danger、alert-warning、alert-info
   * @param time 消失时间
   */
  var prompt = function (message, style, time)
  {
      style = (style === undefined) ? 'alert-success' : style;
      time = (time === undefined) ? 1500 : time*1000;
      $('<div>')
          .appendTo('body')
          .addClass('alert ' + style)
          .html(message)
          .show()
          .delay(time)
          .fadeOut();
  };

  // 成功提示
  var success_prompt = function(message, time)
  {
      prompt(message, 'alert-success', time);
  };

  // 失败提示
  var fail_prompt = function(message, time)
  {
      prompt(message, 'alert-danger', time);
  };

  // 提醒
  var warning_prompt = function(message, time)
  {
      prompt(message, 'alert-warning', time);
  };

  // 信息提示
  var info_prompt = function(message, time)
  {
      prompt(message, 'alert-info', time);
  };

</script>


<!-- fancybox -->
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>
<script>
  let LAZY_LOAD_IMAGE = "";
  $(".article-entry").find("fancybox").find("img").each(function () {
      var element = document.createElement("a");
      $(element).attr("data-fancybox", "gallery");
      $(element).attr("href", $(this).attr("src"));
      /* 图片采用懒加载处理时,
       * 一般图片标签内会有个属性名来存放图片的真实地址，比如 data-original,
       * 那么此处将原本的属性名src替换为对应属性名data-original,
       * 修改如下
       */
       if (LAZY_LOAD_IMAGE) {
         $(element).attr("href", $(this).attr("data-original"));
       }
      $(this).wrap(element);
  });
</script>





  <script>setLoadingBarProgress(100);</script>
  <!-- <script src="https://my.openwrite.cn/js/readmore.js" type="text/javascript"></script>
  <script>
      const btw = new BTWPlugin();
      btw.init({
          id: 'container',
          blogId: '17446-1571644985832-648',
          name: '脑洞前端',
          qrcode: 'https://lucifer-1259702774.cos.ap-shanghai.myqcloud.com/2019-09-19-085421.jpg',
          keyword: 'more',
      });
  </script> -->
</body>
</html>
